package 草稿包;

import java.util.Scanner;

public class MinimizePriceTags {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            for (int i = 0; i < n; i++) {
                b[i] = scanner.nextInt();
            }
            int minTags = minimizePriceTags(a, b, n);
            System.out.println(minTags);
        }
        scanner.close();
    }

    private static int minimizePriceTags(int[] a, int[] b, int n) {
        // dp[i] 表示前i种物品最少需要的标签数
        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            // 初始化为当前物品的数量，因为至少需要这么多标签
            dp[i] = a[i - 1];
            // 尝试不同的组数，找到最少的标签数
            for (int j = 1; j * j <= a[i - 1]; j++) {
                if (a[i - 1] % j == 0) {
                    // 如果j能整除a[i-1]，那么dp[i] = min(dp[i], dp[i-1] + 1)
                    dp[i] = Math.min(dp[i], dp[i - j] + 1);
                    if (j != a[i - 1] / j) {
                        dp[i] = Math.min(dp[i], dp[i - a[i - 1] / j] + 1);
                    }
                }
            }
            // 计算新价格，并更新dp数组
            for (int k = i - 1; k > 0 && b[k] == b[i - 1]; k--) {
                dp[i] = Math.min(dp[i], dp[k - 1] + (a[i - 1] + a[k - 1] - 1) / a[k - 1]);
            }
        }
        return dp[n];
    }
}